The present invention relates to the field of error correction coding and decoding. More particularly, the present invention relates to Low Density Parity Check (LDPC) codes and to an LDPC encoder.
The process of transmitting digital data can introduce errors into the data. As a result, the received data can be different from the transmitted data. Such errors are typically caused by noise that is present in the transmission channel. The amount of errors is generally related to the transmission signal strength in relation to the amount of noise present. Error correction coding is a technique by which redundancy is inserted into the data prior to transmission. Upon reception, this redundancy is used in an attempt to correct errors that were introduced during the transmission process.
Block coding is a type of error correction coding in which the digital data to be transmitted is broken into messages of fixed size. Prior to transmission, each message is encoded into a codeword (also referred to as a “block”) by an encoder. Redundancy, referred to as parity data, is inserted during the encoding process so that the codewords are made larger than the messages. Each codeword includes both message bits and parity bits. Assume that the codewords each consist of n bits. Only certain patterns of n bits are valid codewords; the remaining patterns are invalid. The codewords are then transmitted, which may cause the codewords to become corrupted. Upon reception, a decoder attempts to infer the original messages from the received, and possibly corrupted, codewords.
A generator matrix can be used during the encoding process to encode the messages into valid codewords. Upon reception, a parity check matrix can be used during the decoding process to generate an error vector, where the error vector indicates the presence of errors in the received codeword.
A linear block error correction code is one in which any linear combination of valid codewords is also a valid codeword. Low Density Parity Check (LDPC) codes are a subcategory of linear block error correction codes characterized by a sparse parity check matrix. This means that the parity check matrix consists mainly of 0's and a relatively small number of 1's. LDPC codes were first introduced in the 1960's but have more recently received increased attention. This is due at least in part to inherent parallelism in decoding which makes LDPC codes suitable for hardware implementation and due to flexibility in designing LDPC codes, which allows LDPC codes to be used in a variety of applications. A number of telecommunications standards use a set of LDPC codes having a variety of block lengths and code rates. The code rate can be defined as the portion of non-redundant data contained in each block.
The generator matrix for LDPC codes is generally not sparse. This means that the encoding process for an LDPC code can have high complexity. In an effort to reduce encoding complexity, some encoding schemes use the parity check matrix to compute the codewords during the encoding process. This is possible because the parity check matrix is related to the generator matrix in that the parity check matrix for each particular LDPC code can be derived from the generator matrix for that code. The parity check matrix can be partitioned into sub-matrices. The parity bits for each codeword can be computed from the message bits using the sub-matrices.
Some LDPC encoders employ backward substitution. This approach is used to avoid inversion of the parity check sub-matrix in an effort to reduce complexity of the encoding computations. However, parallelization of the backward substitution procedure introduces high complexity. Also, to implement the backward substitution procedure for LDPC codes having different of block lengths and code rates, at least the non-zero elements for multiple sub-matrices need to be stored (i.e. one per code length, per code rate), which requires large memories. In addition to the storage requirements, implementation of these procedures tends to require complex hardware.